Flip game II [DP, Hash]

Time: O(N+C^2); Space: O(C); medium

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -,

you and your friend take turns to flip two consecutive “++” into “–”.

The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

Example 1:

Input: s = “++++”

Output: True

Explanation:

  • The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

Example 2:

Input: s = “+++++”

Output: False

Explanation:

  • The starting player can not win

  • “+++–” –> “+—-”

  • “++–+” –> “—-+”

Follow up:

  • Derive your algorithm’s runtime complexity.

1. DP

[1]:

import re

class Solution1(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        g, g_final = [0], 0

        for p in list(map(len, re.split('-+', s))):
            while len(g) <= p:
                # Theorem 2: g[game] = g[subgame1]^g[subgame2]^g[subgame3]...
                # and find first missing number.
                g += min(set(range(p)) - {x^y for x, y in zip(g[:len(g)//2], g[-2:-len(g)//2-2:-1])}),

            g_final ^= g[p]

        return g_final > 0  # Theorem 1: First player must win iff g(current_state) != 0

[3]:

sol = Solution1()
s = "++++"
assert sol.canWin(s) == True

2. Hash

  • We have total O(2^c) game strings,

  • and each hash key in hash table would cost O(c),

  • each one has O(c) choices to the next one,

  • and each one would cost O(clogc) to sort,

So we get O((c * 2^c) * (c * clogc)) = O(c^3 * 2^c * logc) time.

To cache the results of all combinations, thus O(c * 2^c) space.

[4]:

import re

class Solution2(object):
    """
    Hash solution
    Time:  O(n + c^3 * 2^c * logc), n is length of string, c is count of "++"
    Space: O(c * 2^c)
    """
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lookup = {}

        def canWinHelper(consecutives):                                         # O(2^c) time
            consecutives = tuple(sorted(c for c in consecutives if c >= 2))     # O(clogc) time
            if consecutives not in lookup:
                lookup[consecutives] = any(not canWinHelper(consecutives[:i] + (j, c-2-j) + consecutives[i+1:])  # O(c) time
                                           for i, c in enumerate(consecutives)  # O(c) time
                                           for j in range(c - 1))               # O(c) time
            return lookup[consecutives]                                         # O(c) time

        # re.findall: O(n) time, canWinHelper: O(c) in depth
        return canWinHelper(map(len, re.findall(r'\+\++', s)))

[5]:

sol = Solution2()
s = "++++"
assert sol.canWin(s) == True

[6]:

class Solution3(object):
    """
    Time:  O(c * n * c!), n is length of string, c is count of "++"
    Space: O(c * n), recursion would be called at most c in depth.
           Besides, it costs n space for modifying string at each depth.
    """
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        i, n = 0, len(s) - 1
        is_win = False
        while not is_win and i < n:                                     # O(n) time
            if s[i] == '+':
                while not is_win and i < n and s[i+1] == '+':           # O(c) time
                     # t(n, c) = c * (t(n, c-1) + n) + n = ...
                     # = c! * t(n, 0) + n * c! * (c + 1) * (1/0! + 1/1! + ... 1/c!)
                     # = n * c! + n * c! * (c + 1) * O(e) = O(c * n * c!)
                    is_win = not self.canWin(s[:i] + '--' + s[i+2:])    # O(n) space
                    i += 1
            i += 1
        return is_win

[7]:

sol = Solution3()
s = "++++"
assert sol.canWin(s) == True